﻿// 0910train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>

using namespace std;


/*
输入描述
输入包括两行数据，如:
0 5 8 9 9 10
5 0 9 9 9 8
1、每行数据以空格分隔，数据个数是2的整数倍，每两个数是一组，代表棋子在棋盘上的坐标
2、坐标的原点在棋盘左上角点，第一个值是行号，范围从0到18；第二个值是列号，范围从0到18
3、举例说明：第一行数据表示三个坐标(0, 5)、(8, 9)、(9, 10)
4、第一行表示黑棋的坐标，第二行表示白棋的坐标。
5、题目保证输入两行数据，无空行且每行按前文要求是偶数个，每个坐标不会超出棋盘范围。

输出描述
8 7
两个数字以空格分隔，第一个数代表黑棋的气数，第二个数代表白棋的气数。

输入
0 5 8 9 9 10
5 0 9 9 9 8
输出
8 7
 */
class Solution01
{
public:
    vector<vector<int>>getPosVec(vector<int>init_vec)
    {
        vector<vector<int>>pos_vec;
        for (int i=0; i<init_vec.size()-1; i+=2)
        {
            vector<int>min_vec;
            min_vec.push_back(init_vec[i]);
            min_vec.push_back(init_vec[i + 1]);
            pos_vec.push_back(min_vec);
        }
        return pos_vec;
    }

    int compute(vector<vector<int>>&pos_vec, vector<vector<bool>>&origin_checked)
    {
        vector<vector<bool>>checked = origin_checked;
        unordered_set<string>pos_set;

        for (auto&min_pos:pos_vec)
        {
            for (auto&dir_vec:DirectionGrid)
            {
                int curr_r = min_pos[0] + dir_vec[0];
                int curr_c = min_pos[1] + dir_vec[1];

                bool is_curr_r = curr_r >= 0 && curr_r < row_size;
                bool is_curr_c = curr_c >= 0 && curr_c < col_size;

                if (is_curr_r && is_curr_c)
                {
                    bool is_visited = checked[curr_r][curr_c];
                    if (!is_visited)
                    {
                        string new_pos_str;
                        new_pos_str += to_string(curr_r);
                        new_pos_str += ',';
                        new_pos_str += to_string(curr_c);

                        //标记已访问
                        checked[curr_r][curr_c] = true;
                        pos_set.insert(new_pos_str);
                    }
                }
                //for (auto&dir_vec:DirectionGrid)
            }
            //for (auto&min_pos:pos_vec)
        }

        int result = pos_set.size();
        return result;
        //compute
    }

    Solution01(vector<int>&black_init_vec, vector<int>&white_init_vec)
    {
        //0-18不越界 未访问
        vector<vector<int>>black_pos_v = getPosVec(black_init_vec);
        vector<vector<int>>white_pos_v = getPosVec(white_init_vec);

        vector<vector<bool>>checked(row_size, vector<bool>(col_size, false));
        //更新checked，已占的位置不能再计算
        for (auto& pos_item : black_pos_v)
        {
            int row = pos_item[0];
            int col = pos_item[1];
            checked[row][col] = true;
        }
        for (auto& pos_item : white_pos_v)
        {
            int row = pos_item[0];
            int col = pos_item[1];
            checked[row][col] = true;
        }

        int black_count = compute(black_pos_v, checked);
        int white_count = compute(white_pos_v, checked);
        
        cout << black_count << ' ' << white_count;
        //Solution01
    }
private:
    int row_size = 19, col_size = 19;
    vector<vector<int>>DirectionGrid = { {-1,0},{1,0},{0,-1},{0,1} };
};


/*
在一长方形停车场内，每个车位上方都有对应监控器，
当且仅当在当前车位或者前后左右四个方向任意一个车位范围停车时，
监控器才需要打开，给出某一时刻停车场的停车分布，请统计最少需要打开多少个监控器

输入
第一行输入 m，n 表示长宽，满足 1 < m, n <= 20；
后面输入 m 行，每行有 n 个 0 或 1 的整数，整数间使用一个空格隔开，表示该行已停车情况，
其中 0表示空位，1 表示已停。
输出
最少需要打开监控器的数量。

输入
3 3
0 0 0
0 1 0
0 0 0
输出
5
 */
class Solution02
{
public:
    void updateResult(vector<vector<int>>& grid, int curr_r, int curr_c)
    {
        if (grid[curr_r][curr_c]==1)
        {
            result += 1;
            return;
        }

        for (auto&dir_vec:DirectionGrid)
        {
            int other_r = curr_r + dir_vec[0];
            int other_c = curr_c + dir_vec[1];

            bool is_other_r = other_r >= 0 && other_r < row_size;
            bool is_other_c = other_c >= 0 && other_c < col_size;

            if (is_other_r && is_other_c)
            {
	            if (grid[other_r][other_c]==1)
	            {
                    result += 1;
                    return;
	            }
            }

        }

        //updateResult
    }

    Solution02(vector<vector<int>>&grid)
    {
        //扫遍每一个点，4个方位有车，那就+1
        row_size = grid.size();
        col_size = grid[0].size();

        for (int r=0; r<row_size; r++)
        {
            for (int c=0; c<col_size; c++)
            {
                updateResult(grid, r, c);
            }
        }
        cout << result;

        //Solution01
    }
private:
    int result = 0;
    int row_size = 0, col_size = 0;
    vector<vector<int>>DirectionGrid{ {-1,0},{1,0},{0,-1},{0,1} };
};


/*
 有 N 块二手市场收集的银饰，每块银饰的重量都是正整数，收集到的银饰会被熔化用于打造新的饰品。
每一回合，从中选出三块最重的银饰，然后一起熔掉
假设银饰的重量分别为 x 、y 和 z，且 x <= y <= z。那么熔掉的可能结果如下：
如果x == y == z，那么三块银饰都会被完全熔掉；
如果x == y且y != z，会剩余重量为z - y的银块无法被熔掉；
如果x != y且y == z，会剩余重量为y - x的银块无法被熔掉；
如果x != y且y != z，会剩余重量为z - y与y - x差值的银块无法被熔掉。
如果剩余两块，返回较大的重量（若两块重量相同，返回任意一块皆可）；
如果只剩下一块，返回该块的重量；如果没有剩下，就返回 0。

输入描述
输入数据为两行
第一行为银饰数组长度 n，1 ≤ n ≤ 40，
第二行为 n 块银饰的重量，重量的取值范围为[1，2000]，重量之间使用空格隔开
输出描述
如果剩余两块，返回较大的重量（若两块重量相同，返回任意一块皆可）；如果只剩下一块，返回该块的重量；如果没有剩下，就返回 0

输入
3
1 1 1
输出
0

输入
3
3 7 10
输出
1

选出 3 7 10，需要计算 (7-3) 和 (10-7) 的差值，即(7-3)-(10-7)=1，
所以数组转换为 [1]，剩余一块，返回该块重量，返回 1
*/
class Solution03
{
public:
    vector<int>getRemain(int x, int y, int z)
    {
        /*
        如果x == y == z，那么三块银饰都会被完全熔掉；
		如果x == y且y != z，会剩余重量为z - y的银块无法被熔掉；
		如果x != y且y == z，会剩余重量为y - x的银块无法被熔掉；
		如果x != y且y != z，会剩余重量为z - y与y - x差值的银块无法被熔掉。
        */
        vector<int>result;
        if (x == y == z) return result;
        if (x==y && y!=z)
        {
            result.push_back(z - y);
        }
        else if (x!=y && y==z)
        {
            result.push_back(y - x);
        }
        else if (x!=y && y!=z)
        {
            int diff = abs((z - y) - (y - x));
            if (diff == 0) return result;
            result.push_back(diff);
        }
        return result;
        //getRemain
    }

    Solution03(vector<int>&origin_vec)
    {
        int v_size = origin_vec.size();

        vector<int>exec_vec = origin_vec;
        while (exec_vec.size()>=3)
        {
            //每一回合，从中选出三块最重的银饰
            sort(exec_vec.begin(), exec_vec.end(), [](int a, int b)
                {
                    return a > b;
                });

            int z = exec_vec[0];
            int y = exec_vec[1];
            int x = exec_vec[2];

            vector<int>remain = getRemain(x, y, z);
            for (int i=3; i<exec_vec.size(); i++)
            {
                remain.push_back(exec_vec[i]);
            }
            exec_vec = remain;
        }

        if (exec_vec.size()==2)
        {
            sort(exec_vec.begin(), exec_vec.end(), [](int a, int b)
                {
                    return a > b;
                });
            cout << exec_vec[0];
            return;
        }
        if (exec_vec.size() == 1)
        {
            cout << exec_vec[0];
            return;
        }
        cout << 0;
	    //Solution03
    }
};

/*
给定一个数组，编写一个函数来计算它的最大N个数与最小N个数的和。你需要对数组进行去重。

输入描述
第一行输入M， M标识数组大小
第二行输入M个数，标识数组内容
第三行输入N，N表达需要计算的最大、最小N个数

输出描述
输出最大N个数与最小N个数的和

补充说明
数组中数字范围[0，1000]
最大N个数与最小N个数不能有重叠，如有重叠返回-1

输入
5
95 88 83 64 100
2
输出
342

7
95 88 83 64 100 100 100
2
 */
class Solution04
{
public:
    Solution04(vector<int>&num_vec, int N)
    {
        //对数组进行去重
        unordered_set<int>num_set;
        for (auto&num:num_vec)
        {
            num_set.insert(num);
        }

        if (num_set.size()<2* N)
        {
            cout << -1;
            return;
        }

        vector<int>sort_vec;
        for (auto&num:num_set)
        {
            sort_vec.push_back(num);
        }
        sort(sort_vec.begin(), sort_vec.end());

        int result = 0;
        for (int i=0; i< N; i++)
        {
            result += sort_vec[i];
        }

        for (int i=sort_vec.size()-1; i> sort_vec.size()-1-N; i--)
        {
            result += sort_vec[i];
        }
        cout << result;
        //Solution04
    }
};


/*
 现有两组服务器A和B，每组有多个算力不同的CPU，
 其中Ai是A组第i个CPU的运算能力，Bi是B组第i个CPU的运算能力
 一组服务器的总算力是各CPU的算力之和。
为了让两组服务器的算力相等，允许从每组各选出一个CPU进行一次交换，
求两组服务器中，用于交换的CPU的算力，并且要求从A组服务器中选出的CPU，算力尽可能小

输入描述
第一行输入为L1和L2，以空格分隔，L1表示A组服务器中的CPU数量，L2表示B组服务器中的CPU数量
第二行输入为A组服务器中各个CPU的算力值，以空格分隔。
第三行输入为B组服务器中各个CPU的算力值，以空格分隔。

输出描述
对于每组测试数据，输出两个整数，以空格分隔，
依次表示A组选出的CPU算力、B组选出的CPU算力，要求从A组选出的CPU的算力尽可能小

输入
3 4
1 2 3
1 2 3 4
输出
1 3
选择A组中的1和B组中的3进行交换，或者选择A组中的2和B组中的4进行交换，
但由于要求A组选择的算力要尽可能地小，所以选择前者
 */
class Solution05
{
public:
    vector<int>getVec(vector<int>&num_vec)
    {
	    //去重
        unordered_set<int>num_set;
        for (auto&num:num_vec)
        {
            num_set.insert(num);
        }
        vector<int>result;
        for (auto&num:num_set)
        {
            result.push_back(num);
        }

        sort(result.begin(), result.end());
        return result;
    }

    int getSum(vector<int>&num_vec)
    {
        int result = 0;
        for (auto&num:num_vec)
        {
            result += num;
        }
        return result;
    }

    Solution05(vector<int>&a_init_vec, vector<int>&b_init_vec)
    {
        //去重
        int sum_a = getSum(a_init_vec);
        int sum_b = getSum(b_init_vec);

        vector<int>a_vec = getVec(a_init_vec);
        vector<int>b_vec = getVec(b_init_vec);

        int result_a = 0, result_b = 0;
        for (int i=0; i<a_vec.size(); i++)
        {
            bool is_find = false;
            for (int j=0; j<b_vec.size(); j++)
            {
                int change_a = sum_a - a_vec[i] + b_vec[j];
                int change_b = sum_b - b_vec[j] + a_vec[i];

                if (change_a==change_b)
                {
                    result_a = a_vec[i];
                    result_b = b_vec[j];
                    is_find = true;
                    break;

                }

            }
            if (is_find) break;

        }

        cout << result_a << ' ' << result_b;
        //Solution05
    }
};


int main()
{
	{
/*
3 4
1 2 3
1 2 3 4
*/
        int a_size, b_size;
        cin >> a_size >> b_size;

        vector<int>a_vec(a_size);
        for (int i=0; i<a_size; i++)
        {
            cin >> a_vec[i];
        }

        vector<int>b_vec(b_size);
        for (int i=0; i<b_size; i++)
        {
            cin >> b_vec[i];
        }

        Solution05 solu(a_vec, b_vec);

        return 0;
	}
	{
        int v_size;
        cin >> v_size;

        vector<int>num_vec(v_size);
        for (int i=0; i<v_size; i++)
        {
            cin >> num_vec[i];
        }

        int N;
        cin >> N;

        Solution04 solu(num_vec, N);

        return 0;
	}
	{
        int v_size;
        cin >> v_size;
        vector<int>num_vec(v_size);
        for (int i=0; i<v_size; i++)
        {
            cin >> num_vec[i];
        }
        Solution03 solu(num_vec);

        return 0;
	}
	{
        int row_size, col_size;
        cin >> row_size >> col_size;

        vector<vector<int>>grid(row_size, vector<int>(col_size));

        for (int r=0; r<row_size; r++)
        {
	        for (int c=0; c<col_size; c++)
	        {
                cin >> grid[r][c];
	        }
        }

        Solution02 solu(grid);

        return 0;
	}
    //0 5 8 9 9 10
	//5 0 9 9 9 8
    //第一行表示黑棋的坐标，第二行表示白棋的坐标
    string input;
    getline(cin, input);
    vector<int>black_init_v;
    stringstream black_sstream(input);
	string token;
    while (black_sstream>>token)
    {
        black_init_v.push_back(stoi(token));
    }
    getline(cin, input);
    stringstream white_sstream(input);
    vector<int>white_init_v;
    while (white_sstream>>token)
    {
        white_init_v.push_back(stoi(token));
    }
    Solution01 solu(black_init_v, white_init_v);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
